In a network environment, a queuing system may be utilized for queuing multiple packets on an output, such as an output port or queue. For example, network switches, routers and various other network devices may include such a queuing system and an output for forwarding in a network environment. The output may be connected to a network and have a maximum bandwidth available for transmitting packets to the network. The queuing system may divide available bandwidth among the received packets based on, for example, priority, destination, and source of the packet.
The available bandwidth of an output may also be divided based on a network user associated with the packet. For example, a network service provider may sell bandwidth of the output to a customer. The network service provider may guarantee that a certain amount of bandwidth will be available to packets sent from the customer. In this case, the guaranteed amount of bandwidth must be reserved for the customer on the aggregated output. When more than one customer is guaranteed bandwidth, the available bandwidth must be divided among the customers. Typically, the queuing system determines whether a customer's use of the aggregated output has exceeded the guaranteed bandwidth for the customer.
A queuing system can include a scheduler for determining whether a customer's use of the output has been exceeded. When a packet is determined to be a committed information rate (CIR) packet, then the customer's guaranteed bandwidth is not exceeded. CIR packets are forwarded to the aggregated output because they are part of the customer's guaranteed bandwidth. Otherwise, if the packet is a non-CIR packet, then the customer's guaranteed bandwidth may be exceeded by forwarding the packet to the output. Non-CIR packets may be sent when excess bandwidth is available on the output.
In order to schedule packets onto an output, the current bandwidth being consumed by packet traffic on the output can be measured. One method for measuring the bandwidth consumed by packet traffic is to use token buckets. A token bucket is a hardware- or software-implemented algorithm that allows packets to be scheduled based on the number of tokens available in a token bucket. Tokens in the token bucket are refreshed at a predetermined rate. As long as there are sufficient tokens available in the token bucket, packets can be transmitted. If the bucket is empty or contains an insufficient number of tokens, packets waiting to be transmitted may be queued until sufficient tokens are present in the token bucket to allow the packet to be transmitted.
A queuing system can include a CIR token bucket and an excess or non-CIR token bucket for determining whether the packet is a CIR packet. If the CIR token bucket has tokens, then the packet is labeled as a CIR packet. If the CIR token bucket does not have tokens, the packet is an excess packet. If the received packet is a low priority packet or forwarded from a congested network, the packet may be labeled as a non-CIR packet. In those instances, irrespective of the CIR token bucket state, the packet is labeled as a non-CIR packet.
Typically, a network service provider reserves a predetermined amount of bandwidth or excess bandwidth for sending customer packets when all of the customers have exceeded their guaranteed amount of bandwidth. The excess bandwidth may be available for sending the stored packets when all received CIR packets have been sent. FIG. 1 is an exemplary queuing system for scheduling customer packets on the excess bandwidth of a shared output. Referring to FIG. 1, the queuing system is receiving a stream of packets 100, 102, 104, and 106 for scheduling by scheduler 108 to queue on an aggregated output 110. Packets 100, 102, 104, and 106 are non-CIR packets. These packets are forwarded by scheduler 108 when the excess bandwidth of output 112 is available. Packets 100, 102, 104, and 106 are forwarded to output 112 in a first-in first-out (FIFO) manner.
One problem associated with current queuing systems, such as the queuing system shown in FIG. 1, is that customers may obtain an unfair proportion of the excess bandwidth. For example, referring to FIG. 1, four customer packets are being forwarded by scheduler 108. Two of the stored packets belong to customer B. The other two packets belong to customers A and C. In this example, it is assumed that customer A, B, and C have their CIR bandwidth requirements met and all of the queued packets are non-CIR packets. In this case, when all of the stored packets have been sent, customer B will have been provided twice the amount of excess bandwidth as customers A and C. Such a result can occur when one customer sends more packet traffic than the other customers. This results in an unfair distribution of customer packets being sent on the excess bandwidth. It is noted that even if each of customers A, B, and C had only one packet but customer B's packets were larger in comparison to customers A and C, then sending one packet of customer B results in higher bandwidth being allocated to customer B.
It can be advantageous to network service to provide the ability to distribute excess bandwidth among the customers sharing bandwidth on an aggregated output queue. One advantage of being able to distribute the excess bandwidth is that excess bandwidth can be sold based on a rate guarantee according to service class. Such distribution can be implemented by utilizing queuing systems with traffic shaping capabilities. FIG. 2 is an exemplary queuing system including traffic shaping capabilities for scheduling customer packets on the excess bandwidth of a shared output. Referring to FIG. 2, the queuing system can include a plurality of queues 200, 202, and 204 for storing non-CIR packets of each customer. For example, queue 200 is assigned to only store the packets of customer A. A scheduler 204 forwards the customer packets from queues 200, 202, and 204 to an output 208 in a round-robin fashion such that the forwarding of packets is equally distributed among the customers for the excess bandwidth. Alternatively, stored packets may be forwarded based on weights. For example, two packets of customer A may be transmitted for every one packet of customer B and every one packet of customer C. Alternatively, the round-robin or weight implementation can be based on byte count rather than packet count since byte count is a more accurate measure of bandwidth. Customer packets for non-CIR traffic may be stored until sent or a queue becomes full. If the queue becomes full, packets for the queue may be killed.
A traffic shaping configuration as described with respect to FIG. 2 can be problematic for a number of reasons. For example, the traffic shaping configuration requires additional memory to store the packets until they can be forwarded. In addition, such a configuration introduces latency in scheduling multiple queues because packets are stored until they can be scheduled. Further, scheduling becomes more complex because packets must be selected from among many of queues associated with many customers.
Accordingly, in light of these difficulties associated with conventional queuing systems, there exists a need for improved methods, systems, and computer program products for allocating excess bandwidth of an output among a plurality of network users.